package com.ma.graph;

import com.ma.graph.mst.UF;

import java.util.Arrays;

/*
 * Kruskal
 *      将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和mst中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入mst集合；
 *      否则，这条边不是最小生成树的一部分，不要把它加入mst集合。
 *
 * 1135、最低连通成本连接所有城市
 *      给定 int n,int[][] connections ---->  无向图  N个城市（1~N）  connections[i] = [city1,city2,cost];
 *      计算联通所有城市最小代价，无法连通返回-1
 */
public class Solution1135 {
    public static int minimumCost(int n, int[][] connections) {
        UF uf = new UF(n + 1);
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        int mst = 0;
        for (int[] connection : connections) {
            int u = connection[0];
            int v = connection[1];
            int cost = connection[2];
            if (uf.connected(u, v)) {
                continue;
            }
            uf.union(u, v);
            mst += cost;
        }
        return uf.getCount() == 2 ? mst : -1;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] connections = {{1, 2, 5}, {1, 3, 6}, {2, 3, 1}};
        System.out.println(minimumCost(n, connections));
    }
}
